package com.yayako.main.struc;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * 最小化DFA
 *
 * @author cyy
 */
public class MinimizeDFA {
    /** 对应的dfa */
    private DFA dfa;
    /** dfa图 */
    private Digraph digraph;
    /** 初态 */
    private int s0;
    /** 终态集合 */
    private List<Integer> f;
    /** 对应的正规式 */
    private String regex;

    public MinimizeDFA(DFA dfa) {
        this.dfa = dfa;
        regex = dfa.getRegex();
        f = new ArrayList<>();

        // 初始划分
        List<Digraph.Vertex> list1 = new ArrayList<>();
        List<Digraph.Vertex> list2 = new ArrayList<>();
        for (Digraph.Vertex vertex : dfa.getGraph().getVertexes()) {
            if (vertex.isFinal()) {
                list2.add(vertex);
            } else {
                list1.add(vertex);
            }
        }

        divide(list1, list2);
    }

    public boolean ifCanReachFinal(String word) {
        return digraph.ifCanReachFinal(word);
    }

    @Override
    public String toString() {
        return "\nMinimizeDFA:\n"
                + "regex = \""
                + regex
                + '\"'
                + "\ns0 = "
                + s0
                + ", "
                + "f = "
                + f
                + ",\nmove = {"
                + digraph
                + "\n}\n";
    }

    private void divide(List<Digraph.Vertex> list, List<Digraph.Vertex> list2) {
        // 状态集修改
        HashMap<List<Integer>, Integer> map = new HashMap<>();
        List<Integer> tmp = new ArrayList<>();
        for (int i = 0; i < dfa.getNormalChar().size(); ++i) {
            tmp.add(0);
        }
        map.put(tmp, 0);
        int g = 0;
        boolean flag = true;
        while (flag) {
            flag = false;
            for (Digraph.Vertex v1 : list) {
                if (!map.containsKey(v1.nextState())) {
                    map.put(v1.nextState(), g++);
                    v1.setmState();
                    flag = true;
                } else {
                    v1.setmState(map.get(v1.nextState()));
                }
            }
        }

        int[] groups = new int[dfa.getGraph().getVertexNum()];
        HashMap<Digraph.Vertex, Integer> v = new HashMap<>();
        int i = -1;
        // 分组
        i = grouping(groups, list, i, v);
        grouping(groups, list2, i, v);

        // 构建图
        digraph = new Digraph(v.size());
        creDigraph(groups, v);

        //        LinkedHashMap<Digraph.Vertex, Integer> map = new LinkedHashMap<>();
        //        int[] groups = new int[dfa.getGraph().getVertexNum()];
        //        int i = -1;
        //        List<Digraph.Vertex> list = dfa.getGraph().getVertexes();
        //        for (Digraph.Vertex vertex : list) {
        //            if (map.containsKey(vertex)) {
        //                groups[vertex.getVal()] = map.get(vertex);
        //            } else {
        //                map.put(vertex, ++i);
        //                groups[vertex.getVal()] = i;
        //            }
        //        }
        //        digraph = new Digraph(map.size());
        //        for (Digraph.Vertex v : map.keySet()) {
        //            i = groups[v.getVal()];
        //            for (Digraph.Vertex.Edge edge : v.getEdges()) {
        //                digraph.addEdge(i, groups[edge.getTo().getVal()], edge.getVal());
        //            }
        //            if (v.isFinal()) {
        //                digraph.getVertex(i).setFinal();
        //                f.add(i);
        //            }
        //        }
    }

    private int grouping(
            int[] groups, List<Digraph.Vertex> list, int i, HashMap<Digraph.Vertex, Integer> v) {
        HashMap<List<Integer>, Integer> states = new HashMap<>();

        for (Digraph.Vertex vertex : list) {
            if (states.containsKey(vertex.nextState())) {
                groups[vertex.getVal()] = states.get(vertex.nextState());
            } else {
                states.put(vertex.nextState(), ++i);
                v.put(vertex, i);
                groups[vertex.getVal()] = i;
            }
        }
        return i;
    }

    private void creDigraph(int[] groups, HashMap<Digraph.Vertex, Integer> v) {
        int i;
        for (Digraph.Vertex vertex : v.keySet()) {
            i = groups[vertex.getVal()];
            for (Digraph.Vertex.Edge edge : vertex.getEdges()) {
                if (edge.getTo() == null) {
                    continue;
                }
                digraph.addEdge(i, groups[edge.getTo().getVal()], edge.getVal());
            }
            if (vertex.isFinal()) {
                digraph.getVertex(i).setFinal();
                f.add(i);
            }
        }
    }
}
